package nowcoder.huawei;

import java.io.FileNotFoundException;
import java.io.FileReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;
import java.util.Stack;

/**
 * @author wuguojian
 * @description
 * https://www.nowcoder.com/practice/97ba57c35e9f4749826dc3befaeae109
 * 给定一个正整数N代表火车数量，0<N<10，接下来输入火车入站的序列，一共N辆火车，每辆火车以数字1-9编号，火车站只有一个方向进出，同时停靠在火车站的列车中，只有后进站的出站了，先进站的才能出站。
 * 要求输出所有火车出站的方案，以字典序排序输出。
 **/
public class HJ77 {
    private static ArrayList<String> result = new ArrayList<String>();
    private static Stack<Integer> stack = new Stack<Integer>();

    public static void main(String[] args) throws FileNotFoundException {
        Scanner in = new Scanner(new FileReader("input/nowcoder_huawei/HJ77.txt"));
//        Scanner in = new Scanner(System.in);
        while (in.hasNext()) {
            result.clear();
            stack.clear();
            int length = in.nextInt();
            int[] cars = new int[length];
            for (int i = 0 ; i < length ; i++){
                cars[i] = in.nextInt();
            }
            handle("", cars, 0, 0);
            Collections.sort(result);
            for (String s : result) {
                System.out.println(s);
            }
        }
    }
    private static void handle(String s, int[] cars, int inCount, int outCount){
        if(outCount == cars.length){
            result.add(s);
        }
        if (!stack.empty()){
            int car = stack.pop();
            handle(s + car + " ", cars, inCount, outCount + 1);
            stack.push(car);
        }
        if (inCount < cars.length) {
            stack.push(cars[inCount]);
            handle(s, cars, inCount + 1, outCount);
            stack.pop();
        }
    }
}
